LZW based compression and decompression algorithms are known in the art for encoding/decoding sequences of 8-bit data (bytes) to codes, where each code represents one or more bytes, respectively. The original LZW (Lempel-Ziv-Welch) algorithm is a lossless data compression and decompression algorithm that is often used to compress images. Extensions of the original LZW algorithm are, for example, LZ77 and LZ78 and other variants of the LZW algorithm are known as LZMW, LZAP and LZWL variants.
During the compression phase a symbol dictionary is created dynamically. The dictionary is not stored with the compressed data set but can be dynamically recreated during the decompression phase.
During the compression phase LZW based algorithms compress sequences of byte characters into encoded data, which will be referred to as symbols hereinafter. A symbol in the encoded data may have a fixed length of 9 to 16 bits, or a variable length increasing from 9 to 16 bits during compression and decompression.
Decompression in the context of this specification means, that sequences of codes including byte characters and symbols are translated back into the original raw data (uncompressed data set). In LZW based algorithms byte characters with a value less than 256 represent raw data directly. Symbols having the values 256 and 257 typically have a special internal meaning (clear, end). Symbols having values larger than 257 include two parts: a first portion which can include a previously defined symbol or a byte character, and a second portion including a byte character, which is the first byte of the next symbol in sequence. A previously defined symbol is already available in the dictionary.
The general method of the LZW based decompression algorithms is using a push-down stack which is also referred to as a last-in-first-out (LIFO) stack. A LIFO stack is a block of memory which is organized in a way that the last data stored in the stack will be output from the stack first. For resolving symbols into the respective uncompressed byte characters (raw data) during the decompression phase, symbols are at least partially pushed into the stack and combined with the existing stack values. Due to the above described usage of the stack the decoded values are retrieved from the stack in the reversed order and are then transformed by a respective software component into the correct order for finally outputting the correct decompressed data set. LZW based decoders, such as currently implemented in LINUX or in FREETYPE libraries (cf., www.freetype.org), use the above push-down stack approach. However, this transformation is time consuming and disadvantageous with regards to the computational efficiency of LZW based decompression systems.